1. Field of the Invention
The present invention is directed to computer processes that identify tasks dynamically. It particularly concerns maintaining lists of tasks thus identified.
2. Background Information
There are many types of computer operations that can be thought of as series of tasks. Sometimes some or most of the tasks to be performed are identifiable only dynamically. That is, some of the tasks can be identified only by performing others of the tasks. Examples of such tasks occur in what has come to be called “garbage collection.” Garbage collection is the automatic reclamation of dynamically allocated memory. Byte code executed by a Java virtual machine, for instance, often calls for memory to be allocated for data “objects” if certain program branches are taken. Subsequently, a point in the byte-code program's execution can be reached at which there is no further possibility that the data stored in that dynamically allocated memory will be used. Without requiring the programmer to provide specific instructions to do so, the virtual machine executing the byte code automatically identifies such “unreachable” objects and reclaims their memory so that objects allocated thereafter can use it.
The general approach employed by the virtual machine's garbage collector is to identify all objects that are reachable and then reclaim memory that no such reachable object occupies. An object is considered reachable if it is referred to by a reference in a “root set” of locations, such as global variables, registers, or the call stack, that are recognized as being inherently reachable.
But an object is also reachable if it is referred to by a reference in a reachable object. So reachable-object identification is a recursive process: the identification of a reachable object can lead to identification of further reachable objects. And, if every reachable object so far identified is thought of as representing a further task, namely, that of identifying any further objects to which it refers, it can be seen that parts of the garbage-collection process include tasks that are only dynamically identifiable.
Now, a reachable object can contain references to more than one other object, and one or more of those may in turn contain multiple object references. So a list of objects (and thus tasks) identified in this fashion must be kept, and size to which such a list can grow is not knowable in advance. The list size is potentially prodigious, so the job of allocating space to the list can be correspondingly onerous.